package com.warningrc.demo;

import java.util.ArrayList;
import java.util.Stack;


public class DFS_2 {
    // 定义图节点类
    static class Node {
        // 节点的值
        int value;
        // 存储该节点的邻接节点列表
        ArrayList<Node> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }
    }
    // 判断无向图是否连通的方法，接受起始节点作为参数
    public static boolean isConnected(Node start) {
        // 创建一个布尔数组来标记节点是否被访问，假设图中最多有100个节点，根据实际情况调整大小
        boolean[] visited = new boolean[100];
        // 调用辅助的dfs方法进行深度优先搜索，并传递访问标记数组
        dfs(start, visited);
        // 遍历访问标记数组
        for (int i = 0; i < visited.length; i++) {
            // 如果节点已被访问且是起始节点，跳过检查
            if (visited[i] && i == start.value) {
                continue;
            }
            // 如果存在未被访问的节点，返回false表示图不连通
            if (!visited[i]) {
                return false;
            }
        }
        // 如果所有节点都被访问，返回true表示图连通
        return true;
    }

    // 辅助的深度优先搜索方法，用于标记从给定节点可达的所有节点
    private static void dfs(Node node, boolean[] visited) {
        // 创建一个栈来辅助深度优先搜索
        Stack<Node> stack = new Stack<>();
        // 将起始节点压入栈
        stack.push(node);
        // 标记起始节点为已访问
        visited[node.value] = true;
        // 当栈不为空时循环
        while (!stack.isEmpty()) {
            // 取出栈顶节点
            Node current = stack.pop();
            // 遍历当前节点的邻接节点
            for (Node neighbor : current.neighbors) {
                // 如果邻接节点未被访问
                if (!visited[neighbor.value]) {
                    // 将邻接节点压入栈
                    stack.push(neighbor);
                    // 标记邻接节点为已访问
                    visited[neighbor.value] = true;
                }
            }
        }
    }
}